package niuke;

/**
 * description:
 * author:张腾
 * date:2021-06-24
 */

/**
 * 给定一个无序单链表，实现单链表的排序(按升序排序)。
 */
public class NC70 {
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head==null || head.next==null) return head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;

        ListNode left = sortInList(head);
        ListNode right = sortInList(newHead);

        ListNode lhead = new ListNode();
        ListNode res = lhead;
        while (left!=null && right!=null){
            if (left.val<right.val){
                lhead.next = left;
                left = left.next;
            }else{
                lhead.next = right;
                right = right.next;
            }
            lhead = lhead.next;
        }
        lhead.next = left!=null?left:right;
        return lhead.next;
    }
}
